{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Triplets That Can Form Two Arrays of Equal XOR"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #hash-table #math #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #哈希表 #数学 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countTriplets"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #形成两个异或相等数组的三元组数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>arr</code> 。</p>\n",
    "\n",
    "<p>现需要从数组中取三个下标 <code>i</code>、<code>j</code> 和 <code>k</code> ，其中 <code>(0 &lt;= i &lt; j &lt;= k &lt; arr.length)</code> 。</p>\n",
    "\n",
    "<p><code>a</code> 和 <code>b</code> 定义如下：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>a = arr[i] ^ arr[i + 1] ^ ... ^ arr[j - 1]</code></li>\n",
    "\t<li><code>b = arr[j] ^ arr[j + 1] ^ ... ^ arr[k]</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>注意：<strong>^</strong> 表示 <strong>按位异或</strong> 操作。</p>\n",
    "\n",
    "<p>请返回能够令 <code>a == b</code> 成立的三元组 (<code>i</code>, <code>j</code> , <code>k</code>) 的数目。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [2,3,1,6,7]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>满足题意的三元组分别是 (0,1,2), (0,2,2), (2,3,4) 以及 (2,4,4)\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [1,1,1,1,1]\n",
    "<strong>输出：</strong>10\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [2,3]\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [1,3,5,7,9]\n",
    "<strong>输出：</strong>3\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 5：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [7,11,12,9,5,2,7,17,22]\n",
    "<strong>输出：</strong>8\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= arr.length &lt;= 300</code></li>\n",
    "\t<li><code>1 &lt;= arr[i] &lt;= 10^8</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-triplets-that-can-form-two-arrays-of-equal-xor](https://leetcode.cn/problems/count-triplets-that-can-form-two-arrays-of-equal-xor/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-triplets-that-can-form-two-arrays-of-equal-xor](https://leetcode.cn/problems/count-triplets-that-can-form-two-arrays-of-equal-xor/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,3,1,6,7]', '[1,1,1,1,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        s = [0]\n",
    "        for val in arr:\n",
    "            s.append(s[-1] ^ val)\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for k in range(i + 1, n):\n",
    "                if s[i] == s[k + 1]:\n",
    "                    ans += k - i\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, arr: List[int]) -> int:\n",
    "        cnt = 0\n",
    "        presum = [0]\n",
    "        for arri in arr:\n",
    "            presum.append(arri^presum[-1])\n",
    "        for i in range(len(arr)-1):\n",
    "            for k in range(i+1, len(arr)):\n",
    "                for j in range(i+1, k+1):\n",
    "                    if presum[j] ^ presum[i] == presum[j] ^ presum[k+1]:\n",
    "                        cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        ans = 0\n",
    "        for j in range(n):\n",
    "            s = 0\n",
    "            for k in range(j, n):\n",
    "                s ^= arr[k]\n",
    "                if s == 0:\n",
    "                    ans += k - j\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            a = 0\n",
    "            for j in range(i, n):\n",
    "                a ^= arr[j]\n",
    "                b = 0\n",
    "                for k in range(j + 1, n):\n",
    "                    b ^= arr[k]\n",
    "                    if a == b:\n",
    "                        ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        s = list()\n",
    "        for val in arr:\n",
    "            if not s:\n",
    "                s.append(val ^ 0)\n",
    "            else:\n",
    "                s.append(val ^ s[-1])\n",
    "\n",
    "        def get(i):\n",
    "            if i < 0:\n",
    "                return 0\n",
    "            else:\n",
    "                return s[i]\n",
    "\n",
    "        result = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                if get(j) == get(i-1):\n",
    "                    result += j - i\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            a = 0\n",
    "            for j in range(i + 1, n):\n",
    "                a ^= arr[j - 1]\n",
    "                b = 0\n",
    "                for k in range(j + 1, n + 1):\n",
    "                    b ^= arr[k - 1]\n",
    "                    if a == b:\n",
    "                        ans += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "\n",
    "        prefix_xor = [0] * (n + 1)\n",
    "        for i in range(1, n + 1):\n",
    "            prefix_xor[i] = prefix_xor[i - 1] ^ arr[i - 1]\n",
    "\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                a = prefix_xor[j] ^ prefix_xor[i]\n",
    "                for k in range(j, n):\n",
    "                    b = prefix_xor[k + 1] ^ prefix_xor[j]\n",
    "                    \n",
    "                    res += a == b\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        s = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            s[i] = s[i - 1] ^ arr[i]\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                for k in range(j, n):\n",
    "                    if s[j - 1] ^ s[i - 1] == s[k] ^ s[j - 1]:\n",
    "                        # print(i, j, k)\n",
    "                        ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, arr: List[int]) -> int:\n",
    "        n=len(arr)\n",
    "        s=[0]\n",
    "\n",
    "        for val in arr:\n",
    "            s.append(s[-1]^val)\n",
    "        \n",
    "        ans=0\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                for k in range(j,n):\n",
    "                    if s[i]==s[k+1]:\n",
    "                        ans+=1\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        prefix = []\n",
    "        a = 0\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            a = a ^ arr[i]\n",
    "            prefix.append(a)\n",
    "        for i in range(n - 1):\n",
    "            for k in range(i + 1, n):\n",
    "                if i:\n",
    "                    result = prefix[k] ^ prefix[i - 1]\n",
    "                else:\n",
    "                    result = prefix[k]\n",
    "                if result == 0:\n",
    "                    ans += (k - i)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, arr: List[int]) -> int:\n",
    "        l, s = Counter(), Counter()\n",
    "        prexor = ans = 0\n",
    "        for k, num in enumerate(arr):\n",
    "            # 将之前的异或结果更新\n",
    "            l[prexor] += 1\n",
    "            s[prexor] += k\n",
    "            # curxor = arr[0] ^ arr[1] ^ ... ^ arr[k]\n",
    "            prexor ^= num\n",
    "            # 之前存在任意的i满足：arr[0] ^ arr[1] ^ ... ^ arr[i] = curxor,\n",
    "            # 那么i到k可以构成一个异或为0的解，他们之间任意一个坐标(除i以为可以作为j)\n",
    "            # 同上面的双重循环解法, 利用数量和坐标距离更新\n",
    "            ans += k * l[prexor] - s[prexor]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        s = [0]\n",
    "        for val in arr:\n",
    "            s.append(s[-1] ^ val)\n",
    "        cnt, total = Counter(), Counter()\n",
    "        res = 0\n",
    "        for k in range(n):\n",
    "            if s[k+1] in cnt:\n",
    "                res += cnt[s[k+1]] * k - total[s[k+1]]\n",
    "            cnt[s[k]] += 1\n",
    "            total[s[k]] += k\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, arr: List[int]) -> int:\n",
    "        cnt, total = Counter(), Counter()\n",
    "        ans = s = 0\n",
    "\n",
    "        for k, val in enumerate(arr):\n",
    "            if (t := s ^ val) in cnt:\n",
    "                ans += cnt[t] * k - total[t]\n",
    "            cnt[s] += 1\n",
    "            total[s] += k\n",
    "            s = t\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        s = [0]\n",
    "        for val in arr:\n",
    "            s.append(s[-1] ^ val)\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                for k in range(j, n):\n",
    "                    if s[i] == s[k + 1]:\n",
    "                        ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, arr: List[int]) -> int:\n",
    "        pre = [0]\n",
    "        for num in arr:\n",
    "            pre.append(pre[-1]^num)\n",
    "        # print(arr)\n",
    "        # print(pre)\n",
    "        n = len(pre)\n",
    "        count = 0\n",
    "        for i in range(1,n):\n",
    "            for j in range(i+1,n):\n",
    "                for k in range(j,n):\n",
    "                    if pre[k]^pre[j-1] == pre[j-1]^pre[i-1]:\n",
    "                        count += 1\n",
    "                        # print(i-1,j-1,k-1)\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, arr: List[int]) -> int:\n",
    "        n=len(arr)\n",
    "        prefix=[0]*(n+1)\n",
    "        nextfix=[0]*(n+1)\n",
    "        for i in range(n):\n",
    "            prefix[i+1]=prefix[i]^arr[i]\n",
    "        count=0\n",
    "        for j in range(n):\n",
    "            for i in range(j):\n",
    "                for k in range(j,n):\n",
    "                    if prefix[j]^prefix[i]==prefix[k+1]^prefix[j]:\n",
    "                        count+=1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        # 初始化前缀异或数组\n",
    "        prefix = [0]\n",
    "        for num in arr:\n",
    "            prefix.append(prefix[-1] ^ num)\n",
    "        \n",
    "        count = 0\n",
    "        # 双重循环遍历所有的 (i, k) 对\n",
    "        for i in range(n):\n",
    "            for k in range(i + 1, n):\n",
    "                # 如果前缀异或结果相同，则找到了一个有效的三元组\n",
    "                if prefix[i] == prefix[k + 1]:\n",
    "                    # (i, j, k) 对于任何 i < j <= k 都是一个有效的三元组\n",
    "                    count += (k - i)\n",
    "        \n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, arr: List[int]) -> int:\n",
    "        m = 0\n",
    "        n = len(arr)\n",
    "        xors = [0] * (n + 1)\n",
    "        for i in range(n): xors[i + 1] = xors[i] ^ arr[i]\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                for k in range(j, n):\n",
    "                    m += xors[i] ^ xors[j] == xors[j] ^ xors[k + 1]\n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, arr: List[int]) -> int:\n",
    "        # 所有相等数之间的间隔，其中0可以和一开始间隔，一开始的地方有一个隐式的0\n",
    "        # (index - 1) * cnt - sum\n",
    "        pref = [*accumulate(arr, xor, initial=0)]\n",
    "        ans = 0\n",
    "        d = defaultdict(lambda: [0, 0]) # 第一个数是cnt，表示这个数出现的次数，第二个是sum，表示这个数的下标总和\n",
    "        for i, n in enumerate(pref):\n",
    "            ans += (i - 1) * d[n][0] - d[n][1]\n",
    "            d[n][0] += 1\n",
    "            d[n][1] += i\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        s = [0] * (n+1)\n",
    "        for i, a in enumerate(arr):\n",
    "            s[i+1] = s[i] ^ a\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                for k in range(j, n):\n",
    "                    if s[i] == s[k+1]:\n",
    "                        ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, arr: List[int]) -> int:\n",
    "        ans=0\n",
    "        for i in range(len(arr)):\n",
    "            res = arr[i]\n",
    "            for j in range(i+1,len(arr)):\n",
    "                res ^= arr[j]\n",
    "                if res == 0:\n",
    "                    ans += j - i\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        g = [0]\n",
    "        for val in arr:\n",
    "            g.append(g[-1] ^ val)\n",
    "\n",
    "        ans = 0\n",
    "        cnt, total = Counter(), Counter()\n",
    "        for k in range(n):\n",
    "            if g[k + 1] in cnt:\n",
    "                ans += cnt[g[k+1]] * k - total[g[k+1]]\n",
    "            cnt[g[k]] += 1\n",
    "            total[g[k]] += k\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, arr: List[int]) -> int:\n",
    "        #copy\n",
    "        n = len(arr)\n",
    "        s = [0]\n",
    "        for val in arr:\n",
    "            s.append(s[-1]^val)\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                for k in range(j,n):\n",
    "                    if s[i] == s[k+1]:\n",
    "                        ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            temp = arr[i]\n",
    "            for j in range(i + 1, n):\n",
    "                temp ^= arr[j]\n",
    "                if temp == 0:\n",
    "                    ans += (j - i)\n",
    "        return ans\n",
    "        \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, arr: List[int]) -> int:\n",
    "        xorRes = arr[:]\n",
    "        for i in range(1, len(arr)):\n",
    "            xorRes[i] = xorRes[i-1] ^ arr[i]\n",
    "        ans = 0\n",
    "        for i in range(0, len(arr)-1):\n",
    "            for k in range(len(arr)-1, i, -1):\n",
    "                for j in range(i + 1, k + 1):\n",
    "                    a = xorRes[j - 1] ^ xorRes[i] ^ arr[i]\n",
    "                    b = xorRes[k] ^ xorRes[j-1]\n",
    "                    if a == b:\n",
    "                        ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        s = [0]\n",
    "        for val in arr:\n",
    "            s.append(s[-1] ^ val)\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                for k in range(j, n):\n",
    "                    if s[i] == s[k + 1]:\n",
    "                        ans += 1\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        s = [0]\n",
    "        for val in arr:\n",
    "            s.append(s[-1] ^ val)\n",
    "        result = 0\n",
    "        for i in range(n):\n",
    "            for k in range(i+1, n):\n",
    "                if s[k+1] == s[i]:\n",
    "                    result += k - i\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, arr: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        a = arr[i] ^ arr[i + 1] ^ ... ^ arr[j - 1]\n",
    "          = xor_prefix[j] ^ xor_prefix[i]\n",
    "        b = arr[j] ^ arr[j + 1] ^ ... ^ arr[k]\n",
    "          = xor_prefix[k + 1] ^ xor_prefix[j]\n",
    "\n",
    "        a == b\n",
    "\n",
    "        <=> xor_prefix[j] ^ xor_prefix[i] == xor_prefix[k + 1] ^ xor_prefix[j]\n",
    "        <=> xor_prefix[i] == xor_prefix[k + 1]\n",
    "\n",
    "        也就是说，\n",
    "        当 xor_prefix[i] == xor_prefix[k + 1] 时，\n",
    "        对于所有 i < j <= k，均有：\n",
    "            xor_prefix[j] ^ xor_prefix[i] == xor_prefix[k + 1] ^ xor_prefix[j]\n",
    "        即有：\n",
    "            a == b\n",
    "\n",
    "        于是，满足 a == b 成立的三元组 (i, j, k) 个数为： \n",
    "            k - i\n",
    "\n",
    "        \"\"\"\n",
    "        n = len(arr)\n",
    "\n",
    "        prefix_xor = [0] * (n + 1)\n",
    "        for i in range(1, n + 1):\n",
    "            prefix_xor[i] = prefix_xor[i - 1] ^ arr[i - 1]\n",
    "\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for k in range(i + 1, n):\n",
    "                res += (k - i) * (\n",
    "                    prefix_xor[k + 1] == prefix_xor[i]\n",
    "                )\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        preor = [0] * (n+1)\n",
    "        for i in range(n):\n",
    "            preor[i+1] = preor[i] ^ arr[i]\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                for k in range(j, n):\n",
    "                    # 区间为[i, j-1] 和[j, k]\n",
    "                    if (preor[j] ^ preor[i]) == (preor[k+1] ^ preor[j]):\n",
    "                        res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, arr: List[int]) -> int:\n",
    "        result = 0\n",
    "        mapping = {0:[-1]}\n",
    "        pre = 0\n",
    "        for i, a in enumerate(arr):\n",
    "            pre = pre ^ a \n",
    "            if(pre not in mapping):\n",
    "                mapping[pre] = []\n",
    "            for j in mapping[pre]:\n",
    "                result += i-j-1\n",
    "            mapping[pre].append(i)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        s = [0]\n",
    "        for val in arr:\n",
    "            s.append(s[-1] ^ val)\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                for k in range(j, n):\n",
    "                    if s[i] == s[k + 1]:\n",
    "                        ans += 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, arr: List[int]) -> int:\n",
    "        pre,cur=[0],0\n",
    "        for num in arr:\n",
    "            cur^=num\n",
    "            pre.append(cur)\n",
    "        cnt=0\n",
    "        for i in range(len(arr)-1):\n",
    "            for j in range(i+1,len(arr)):\n",
    "                for k in range(j,len(arr)):\n",
    "                    a=pre[j]^pre[i]\n",
    "                    b=pre[k+1]^pre[j]\n",
    "                    if a==b: cnt+=1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        prexor = [0] * (n+1)\n",
    "        for i in range(n):\n",
    "            prexor[i+1] = prexor[i] ^ arr[i]\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for k in range(i+1, n):\n",
    "                if prexor[k+1] ^ prexor[i] == 0:\n",
    "                    res += (k - i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, arr: List[int]) -> int:\n",
    "        n=len(arr)\n",
    "        p=[0]\n",
    "        for a in arr:\n",
    "            p.append(p[-1]^a)\n",
    "        res=0\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                for k in range(j,n):\n",
    "                    if (p[j]^p[i])==(p[k+1]^p[j]):\n",
    "                        res+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        s = [0]\n",
    "        for val in arr:\n",
    "            s.append(s[-1] ^ val)\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                for k in range(j, n):\n",
    "                    if s[i] == s[k + 1]:\n",
    "                        ans += 1\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        s = [0]\n",
    "        for val in arr:\n",
    "            s.append(s[-1] ^ val)\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for k in range(i + 1, n):\n",
    "                if s[i] == s[k + 1]:\n",
    "                    ans += k - i\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # def countTriplets(self, arr: List[int]) -> int:\n",
    "    #     n = len(arr)\n",
    "    #     pre = list(accumulate(arr, func=operator.xor, initial=0))\n",
    "    #     ans = 0\n",
    "    #     for i in range(n):\n",
    "    #         for j in range(i + 1, n):\n",
    "    #             for k in range(j, n):\n",
    "    #                 if pre[j] ^ pre[i] == pre[k + 1] ^ pre[j]:\n",
    "    #                     ans += 1\n",
    "    #     return ans\n",
    "\n",
    "    def countTriplets(self, arr: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        a = b\n",
    "        => a ^ b == 0\n",
    "        => arr[i] ^ arr[i + 1] ^ ... ^ arr[j] ^ ... arr[k] == 0\n",
    "        \"\"\"\n",
    "        n = len(arr)\n",
    "        pre = list(accumulate(arr, func=operator.xor, initial=0))\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                if pre[j + 1] ^ pre[i] == 0:\n",
    "                    ans += j - i\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, arr: List[int]) -> int:\n",
    "        # 先把前缀异或求出来\n",
    "        tm = 0\n",
    "        pre = []\n",
    "        for x in arr:\n",
    "            tm ^= x\n",
    "            pre.append(tm)\n",
    "        print(pre)\n",
    "\n",
    "\n",
    "        # a==b --->>a^b =0  ---->>pre[i-1]^pre[k]=0\n",
    "        n = len(arr)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for k in range(i+1, n):\n",
    "                if i == 0:\n",
    "                    tm = pre[k]\n",
    "                else:\n",
    "                    tm = pre[i-1]^pre[k]\n",
    "                if tm == 0:\n",
    "                    res += k-i\n",
    "        return res\n",
    "\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        preXor = [0]\n",
    "        for i in range(n):\n",
    "            preXor.append(preXor[-1]^arr[i])\n",
    "        ans = 0\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(i+1, n+1):\n",
    "                for k in range(j, n+1):\n",
    "                    a = preXor[j-1]^preXor[i-1]\n",
    "                    b = preXor[k]^preXor[j-1]\n",
    "                    ans += (a==b)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        s = [0]\n",
    "        for val in arr:\n",
    "            s.append(s[-1] ^ val)\n",
    "        \n",
    "        cnt, total = Counter(), Counter()\n",
    "        ans = 0\n",
    "        for k in range(n):\n",
    "            if s[k+ 1] in cnt:\n",
    "                ans += cnt[s[k+1]] * k - total[s[k+1]]\n",
    "            cnt[s[k]] += 1\n",
    "            total[s[k]] += k\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, arr: List[int]) -> int:\n",
    "        n=len(arr)\n",
    "        ans=0\n",
    "        temp=[0]*(n+1)\n",
    "        for i in range(n):\n",
    "            temp[i+1]=temp[i]^arr[i]\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1,n):\n",
    "                for k in range(j,n):\n",
    "                    if (temp[i]^temp[j+1])==(temp[k+1]^temp[j+1]):\n",
    "                        ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        pre = list(accumulate(arr, func=operator.xor, initial=0))\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                for k in range(j, n):\n",
    "                    if pre[j] ^ pre[i] == pre[k + 1] ^ pre[j]:\n",
    "                        ans += 1\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, arr: List[int]) -> int:\n",
    "        # 所有相等数之间的间隔，其中0可以和一开始间隔，一开始的地方有一个隐式的0\n",
    "        # (index - 1) * cnt - sum   每个数的贡献\n",
    "        ans = 0\n",
    "        d = defaultdict(lambda: [0, 0]) # 第一个数是cnt，表示这个数出现的次数，第二个是sum，表示这个数的下标总和\n",
    "        for i, n in enumerate(accumulate(arr, xor, initial=0)):\n",
    "            ans += (i - 1) * d[n][0] - d[n][1]\n",
    "            d[n][0] += 1\n",
    "            d[n][1] += i\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, arr: List[int]) -> int:\n",
    "        ret = 0        \n",
    "        for i in range(len(arr)-1):\n",
    "            for j in range(i+1, len(arr)):\n",
    "                for k in range(j, len(arr)):\n",
    "                    a, b = arr[i], arr[j]\n",
    "                    for x in range(i+1, j):\n",
    "                        a ^= arr[x]\n",
    "                    for y in range(j+1, k+1):\n",
    "                        b ^= arr[y]\n",
    "                    if a == b: ret += 1\n",
    "        return ret\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        cur = [0] * (n+1)\n",
    "        for i in range(1, n+1):\n",
    "            cur[i] = cur[i-1] ^ arr[i-1]\n",
    "        ret = 0        \n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1, n):\n",
    "                for k in range(j, n):\n",
    "                    a = cur[i] ^ cur[j]\n",
    "                    b = cur[j] ^ cur[k+1]\n",
    "                    if a == b: ret += 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, arr: List[int]) -> int:\n",
    "        result = 0\n",
    "        mapping = {0:[-1]}\n",
    "        pre = 0\n",
    "        for i, a in enumerate(arr):\n",
    "            pre = pre ^ a \n",
    "            if(pre not in mapping):\n",
    "                mapping[pre] = []\n",
    "            for j in mapping[pre]:\n",
    "                result += i-j-1\n",
    "            mapping[pre].append(i)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, arr: List[int]) -> int:\n",
    "        ret = 0        \n",
    "        for i in range(len(arr)-1):\n",
    "            for j in range(i+1, len(arr)):\n",
    "                for k in range(j, len(arr)):\n",
    "                    a, b = arr[i], arr[j]\n",
    "                    for x in range(i+1, j):\n",
    "                        a ^= arr[x]\n",
    "                    for y in range(j+1, k+1):\n",
    "                        b ^= arr[y]\n",
    "                    if a == b: ret += 1\n",
    "        return ret\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        cur = [0] * (n+1)\n",
    "        for i in range(1, n+1):\n",
    "            cur[i] = cur[i-1] ^ arr[i-1]\n",
    "        ret = 0        \n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1, n):\n",
    "                for k in range(j, n):\n",
    "                    a = cur[i] ^ cur[j]\n",
    "                    b = cur[j] ^ cur[k+1]\n",
    "                    if a == b: ret += 1\n",
    "        return ret\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        cur = [0] * (n+1)\n",
    "        for i in range(1, n+1):\n",
    "            cur[i] = cur[i-1] ^ arr[i-1]\n",
    "        ret = 0        \n",
    "        for i in range(n-1):\n",
    "            for k in range(i+1, n):\n",
    "                if cur[i] == cur[k+1]: ret += k-i\n",
    "        return ret"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
